package com.da.javatest.niuke.jianzhi;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import com.da.javatest.niuke.common.TreeNode;

/**
 * @author chenlida
 * @date 2020/10/27 10:08
 * https://www.nowcoder.com/practice/ef068f602dde4d28aab2b210e859150a?
 * tpId=13&tags=&title=&diffculty=0&judgeStatus=0&rp=1
 */
public class C62Solution {
    public TreeNode KthNode(TreeNode pRoot, int k) {
        List<Integer> list = new ArrayList<>();
        getAllData(list, pRoot);
        if (k < 1 || k > list.size()) {
            return null;
        }
        return new TreeNode(list.get(k - 1));
    }

    /**
     * 二叉搜索树的中序遍历就是树节点值的递增排列！
     */
    private void getAllData(List<Integer> list, TreeNode node) {
        if (node != null) {
            getAllData(list, node.left);
            list.add(node.val);
            getAllData(list, node.right);
        }
    }

    public TreeNode KthNode2(TreeNode pRoot, int k) {
        int count = 0;
        if (pRoot == null || k <= 0) {
            return null;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = pRoot;
        //中序遍历
        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                stack.push(node); //当前节点不为null，应该寻找左子节点，准备让左子节点入栈
                node = node.left;
            } else {
                node = stack.pop();//当前节点null则弹出栈内元素，相当于按顺序输出最小值。
                count++;//弹出时，才应该计数
                if (count == k) { //相等时就返回
                    return node;
                }
                node = node.right;//左边遍历完，还没到K，就得找右子节点
            }
        }
        return null;
    }
}
